import java.util.Arrays;

/**
 * @author tmh
 * @date 2024/9/24 16:02
 * @description 有重复数组说明有环，第一个while就是找到相遇的的地方
 * 第二个while就是找到重复数字的第一个数
 * 根据弗洛伊德环检测算法，快慢指针相遇后，将一个指针从起点出发，另一个从相遇点出发，它们一定会在环的起点相遇。
 */
public class T287寻找重复数 {
    public static void main(String[] args) {
        int num = 4 ^ 2;
        System.out.println(num);
    }

    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        //给slow和fast赋初值
        slow=nums[slow];
        fast=nums[nums[fast]];
        while (slow != fast) {
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        int pre1=0;
        int pre2=slow;
        while (pre1!=pre2){
            pre1=nums[pre1];
            pre2=nums[pre2];
        }
        return pre1;
    }
}
